class DynamicProgramming:
    
    def fibonacci(self, n: int) -> int:
        """
        斐波那契数列 - 动态规划实现
        时间复杂度: O(n)
        空间复杂度: O(1)
        """
        if n <= 1:
            return n
        
        # 使用滚动数组优化空间
        prev, curr = 0, 1
        for i in range(2, n + 1):
            prev, curr = curr, prev + curr
        
        return curr
    
    def knapSack(self, capacity: int, weights: list, values: list) -> int:
        """
        0-1背包问题 - 动态规划实现
        capacity: 背包容量
        weights: 物品重量列表
        values: 物品价值列表
        时间复杂度: O(n * capacity)
        空间复杂度: O(capacity)
        """
        n = len(weights)
        # dp[i] 表示容量为i时的最大价值
        dp = [0] * (capacity + 1)
        
        for i in range(n):
            # 倒序遍历，避免重复选择
            for j in range(capacity, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
        
        return dp[capacity]
    
    def coinChange(self, coins: list, amount: int) -> int:
        """
        零钱兑换问题 - 动态规划实现
        求凑成amount所需的最少硬币数
        时间复杂度: O(n * amount)
        空间复杂度: O(amount)
        """
        # dp[i] 表示凑成金额i所需的最少硬币数
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # 金额0需要0个硬币
        
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != float('inf') else -1

if __name__ == "__main__":
    dp = DynamicProgramming()
    
    # 测试斐波那契数列
    print("斐波那契数列:")
    for i in range(10):
        print(f"F({i}) = {dp.fibonacci(i)}")
    
    # 测试背包问题
    print("\n背包问题:")
    capacity = 10
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    max_value = dp.knapSack(capacity, weights, values)
    print(f"最大价值: {max_value}")
    
    # 测试零钱兑换
    print("\n零钱兑换:")
    coins = [1, 2, 5]
    amount = 11
    min_coins = dp.coinChange(coins, amount)
    print(f"最少硬币数: {min_coins}")